
#ifndef BIGINTEGER_HPP_WINSTJACKONW
#define BIGINTEGER_HPP_WINSTJACKONW

#include <algorithm>
#include <cassert>
#include <compare>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <format>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string_view>
#include <vector>

namespace WinstJackonw {

namespace _details {
static constexpr auto base{10};
}
template <typename AddTemporaryIntegral, typename MulTempIntegral,
          long long base>
concept IsResultOverflow =
    std::numeric_limits<AddTemporaryIntegral>::max() >= 2 * base - 1 &&
    std::numeric_limits<MulTempIntegral>::max() >= base * base - 1;

template <typename T>
consteval auto comptime_pow(T base, std::size_t pow) -> T {
  return pow == 1 ? base : base * comptime_pow(base, pow - 1);
}

template <std::signed_integral TSignedIntegral = std::int32_t,
          typename Container = std::vector<TSignedIntegral>,
          std::signed_integral AddTemporaryIntegral = std::int32_t,
          std::signed_integral MulTempIntegral = std::int64_t,
          std::size_t base_exponent = 4>
  requires IsResultOverflow<AddTemporaryIntegral, MulTempIntegral,
                            comptime_pow(TSignedIntegral{_details::base},
                                         base_exponent)>
class BigInteger {
 public:
  static constexpr auto radix = _details::base;
  static constexpr std::size_t base_exp = base_exponent;
  static constexpr TSignedIntegral base =
      comptime_pow(TSignedIntegral{10}, base_exp);

 private:
  Container data;
  bool neg;

  constexpr void shrink() {
    while (data.size() > 1 && data.back() == 0) {
      data.pop_back();
    }
    correct_zero_sign();
  }
  constexpr void correct_zero_sign() noexcept {
    if (data.size() == 1 && data.front() == 0) {
      neg = false;
    }
  }

 public:
  constexpr BigInteger() : data{0}, neg{false} {}
  explicit constexpr BigInteger(std::string_view s) : data{}, neg{false} {
    if (s.empty()) {
      neg = false;
      data.push_back(0);
      return;
    }

    std::size_t start{0};
    if (s[0] == '-') {
      neg = true;
      start = 1;
    } else if (s[0] == '+') {
      neg = false;
      start = 1;
    }
    while (start < s.size() && s[start] == '0') ++start;
    if (start == s.size()) {
      neg = false;
      data.push_back(0);
      return;
    }

    auto len = s.size() - start;
    auto num_digits = (len + base_exp - 1) / base_exp;

    for (std::size_t i{0}; i < num_digits; ++i) {
      std::size_t chunk_start = s.size() - std::min(len, (i + 1) * base_exp);
      std::size_t chunk_end = s.size() - i * base_exp;
      std::string_view chunk_str =
          s.substr(chunk_start, chunk_end - chunk_start);
      std::int32_t chunk_value = 0;
      std::int32_t multiplier = 1;
      for (auto it = chunk_str.rbegin(); it != chunk_str.rend(); ++it) {
        if (*it >= '0' && *it <= '9') {
          chunk_value += static_cast<std::int32_t>(*it - '0') * multiplier;
          multiplier *= radix;
        } else {
          throw std::runtime_error("Failed to parse number");
        }
      }
      data.push_back(chunk_value);
    }
    while (data.size() > 1 && data.back() == 0) {
      data.pop_back();
    }
    if (data.size() == 1 && data.front() == 0) {
      neg = false;
    }
  }
  template <std::signed_integral T>
  /*explicit*/ constexpr BigInteger(T x) : data{} {
    std::make_unsigned_t<T> x_abs;
    if (x < 0) {
      neg = true;
      x_abs = -x;
    } else {
      neg = false;
      x_abs = x;
    }
    do {
      data.push_back(x_abs % base);
      x_abs /= base;
    } while (x_abs);
  }
  template <std::unsigned_integral T>
  /*explicit*/ constexpr BigInteger(T abs_x) : data{}, neg(false) {
    do {
      data.push_back(abs_x % base);
      abs_x /= base;
    } while (abs_x);
  }
  template <typename... Args>
  explicit constexpr BigInteger(const BigInteger<Args...>& rhs)
      : data(rhs.data.size()), neg(rhs.neg) {
    std::ranges::copy(rhs.data, data);
  }
  constexpr bool is_negative() const noexcept { return neg; }
  constexpr bool is_zero() const noexcept {
    return data.size() == 1 && data.front() == 0;
  }
  constexpr std::string to_string() const noexcept(false) {
    return std::format("{}", *this);
  }
  constexpr BigInteger get_abs() const {
    BigInteger result = *this;
    result.neg = false;
    return result;
  }
  constexpr std::strong_ordering compare_abs(const BigInteger& rhs) const {
    if (data.size() != rhs.data.size()) return data.size() <=> rhs.data.size();
    for (auto it{data.crbegin()}, rit{rhs.data.crbegin()}; it != data.crend();
         ++it, ++rit) {
      if (*it != *rit) return *it <=> *rit;
    }
    return std::strong_ordering::equivalent;
  }
  constexpr BigInteger add_abs(const BigInteger& rhs) const {
    BigInteger res;
    res.data.clear();
    TSignedIntegral carry = 0;
    auto it = data.begin();
    auto rhs_it = rhs.data.begin();

    while (it != data.end() || rhs_it != rhs.data.end() || carry != 0) {
      TSignedIntegral sum = carry;
      if (it != data.end()) {
        sum += *it;
        ++it;
      }
      if (rhs_it != rhs.data.end()) {
        sum += *rhs_it;
        ++rhs_it;
      }
      carry = sum / base;
      TSignedIntegral digit = sum % base;
      res.data.push_back(digit);
    }
    return res;
  }
  constexpr BigInteger sub_abs(const BigInteger& rhs) const {
    BigInteger result = *this;
    TSignedIntegral borrow = 0;
    auto it = result.data.begin();
    auto rhs_it = rhs.data.cbegin();
    for (; it != result.data.end();
         ++it, (rhs_it != rhs.data.end() ? ++rhs_it : rhs_it)) {
      TSignedIntegral other_digit = (rhs_it != rhs.data.end()) ? *rhs_it : 0;
      *it -= borrow + other_digit;
      if (*it < 0) {
        *it += base;
        borrow = 1;
      } else {
        borrow = 0;
      }
    }
    result.shrink();
    return result;
  }
  constexpr bool operator==(const BigInteger& rhs) const {
    if (data.size() != rhs.data.size() || neg != rhs.neg) return false;
    auto it1 = data.begin();
    auto it2 = rhs.data.begin();
    while (it1 != data.end() && it2 != rhs.data.end()) {
      if (*it1 != *it2) return false;
      ++it1;
      ++it2;
    }
    return true;
  }
  constexpr bool operator!=(const BigInteger& x) const { return !(*this == x); }
  constexpr std::strong_ordering operator<=>(
      const BigInteger& rhs) const noexcept {
    if (neg != rhs.neg)
      return neg ? std::strong_ordering::less : std::strong_ordering::greater;
    return neg ? rhs.compare_abs(*this) : compare_abs(rhs);
  }
  constexpr BigInteger operator+(const BigInteger& rhs) const {
    if (neg == rhs.neg) {
      BigInteger result = add_abs(rhs);
      result.neg = neg;
      return result;
    }
    std::strong_ordering cmp_result = compare_abs(rhs);
    if (cmp_result == std::strong_ordering::equivalent) return BigInteger();

    BigInteger result = cmp_result > 0 ? sub_abs(rhs) : rhs.sub_abs(*this);
    result.neg = cmp_result > 0 ? neg : rhs.neg;
    return result;
  }
  constexpr BigInteger operator-(const BigInteger& rhs) const {
    return *this + (-rhs);
  }
  constexpr BigInteger operator-() const noexcept {
    if (is_zero()) return *this;

    BigInteger result = *this;
    result.neg = !result.neg;
    return result;
  }
  constexpr BigInteger operator*(const BigInteger& rhs) const noexcept(false) {
    BigInteger res;
    res.data.resize(data.size() + rhs.data.size(), 0);
    auto this_it = data.begin();
    auto res_it = res.data.begin();
    for (std::size_t i = 0; i < data.size(); ++i, ++this_it, ++res_it) {
      MulTempIntegral carry = 0;
      auto other_it = rhs.data.begin();
      auto result_pos_it = res_it;
      for (std::size_t j = 0; j < rhs.data.size() || carry;
           ++j, ++result_pos_it) {
        MulTempIntegral rhs_num = (j < rhs.data.size()) ? *other_it : 0;
        MulTempIntegral product = *result_pos_it + carry + (*this_it) * rhs_num;
        carry = product / base;
        *result_pos_it = product % base;
        if (j < rhs.data.size()) ++other_it;
      }
    }
    res.shrink();
    res.neg = neg != rhs.neg;
    res.correct_zero_sign();
    return res;
  }
  constexpr BigInteger operator/(const BigInteger& divisor) const
      noexcept(false) {
    if (divisor == BigInteger()) throw std::runtime_error("??");

    if (compare_abs(divisor) < 0) return BigInteger();
    constexpr bool isUsingPushFront = requires { Container{}.push_front(0); };
    constexpr bool isUsingPushBack =
        !isUsingPushFront && requires { Container{}.push_back(0); };
    BigInteger dividend = get_abs();
    BigInteger divisor_abs = divisor.get_abs();
    BigInteger quotient;
    BigInteger remainder;
    quotient.data.clear();
    for (auto it = dividend.data.rbegin(); it != dividend.data.rend(); ++it) {
      remainder = remainder * base + *it;
      TSignedIntegral digit = 0;
      TSignedIntegral low = 0;
      TSignedIntegral high = base - 1;
      while (low <= high) {
        TSignedIntegral mid = (low + high) / 2;
        BigInteger product = divisor_abs * mid;
        if (product <= remainder) {
          digit = mid;
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      if constexpr (isUsingPushFront) {
        quotient.data.push_front(digit);
      } else if constexpr (isUsingPushBack) {
        quotient.data.push_back(digit);
      } else {
        throw "???";
      }
      remainder = remainder - divisor_abs * digit;
    }

    if constexpr (isUsingPushBack) std::ranges::reverse(quotient.data);
    quotient.shrink();
    quotient.neg = neg != divisor.neg;
    quotient.correct_zero_sign();
    return quotient;
  }

  // formatter
  friend std::ostream& operator<<(std::ostream& os, const BigInteger& num) {
    if (num.neg) os << '-';
    os << num.data.back();
    for (auto it = ++num.data.rbegin(); it != num.data.rend(); ++it) {
      os << std::setw(base_exp) << std::setfill('0') << *it;
    }
    return os;
  }

  template <typename CharT>
  static constexpr auto parse(std::basic_format_parse_context<CharT>& ctx) {
    return ctx.begin();
  }
  template <typename FormatContext>
  auto format(FormatContext& ctx) const {
    auto out = ctx.out();
    if (neg) {
      out = std::format_to(out, "-");
    }
    out = std::format_to(out, "{}", data.back());
    for (auto it = ++data.rbegin(); it != data.rend(); ++it) {
      out = std::format_to(
          out, "{:0{}}", *it,
          WinstJackonw::BigInteger<TSignedIntegral, Container>::base_exp);
    }
    return out;
  }
};

}  // namespace WinstJackonw
namespace std {
using WinstJackonw::BigInteger;
template <typename U, typename C, typename CharT>
struct formatter<BigInteger<U, C>, CharT> {
  constexpr auto parse(std::basic_format_parse_context<CharT>& ctx) {
    return BigInteger<U, C>::parse(ctx);
  }
  template <typename FormatContext>
  auto format(const BigInteger<U, C>& num, FormatContext& ctx) const {
    return num.format(ctx);
  }
};
}  // namespace std

#endif  // BIGINTEGER_HPP_WINSTJACKONW